A cache memory is a relatively small, high speed memory used as a buffer between a central processing unit (CPU) and a main memory in order to increase operating speed. The cache memory has an access time which is substantially shorter than the access time of the main memory. The utility of the cache memory arises from the fact that computer programs have a tendency to reference localized areas of main memory over a given interval of time. By transferring that localized area of main memory to the faster cache memory for access by the CPU, overall operating speed is increased.
When a cache memory is used, the CPU looks for a referenced memory location in the cache memory. When the referenced address is found in the cache memory, known as a cache hit, the program proceeds normally. When the referenced memory location is not found in the cache memory, known as a cache miss, the referenced memory location must be accessed in the main memory. When a miss occurs, the data from the referenced location can be placed in the cache memory for future use. Data can also be stored in the cache memory under program control without first detecting a miss.
Cache memories are commonly sized to correspond to a multiple of virtual memory pages. A page of memory is made up of a multiple of blocks, and within a page there is a one-to-one correspondence between virtual memory blocks and physical memory blocks. The cache memory will hold a copy of data from main memory along with a corresponding tag identifying the page of main memory. The cache index address identifies the location of the block within a group of consecutive virtual memory pages. Thus, the cache memory stores a tag field and a data field. To increase the effectiveness of the cache memory, it is known to use a set associative mapping technique wherein two or more cache memory elements provide a set of cache cells at each cache index address location. With this arrangement, data from two or more main memory blocks can be stored at a given cache index address. When the CPU attempts to store a main memory word in cache memory, there are two or more possible locations in the set where the word can be stored. This arrangement reduces "thrashing" wherein memory words are constantly swapped in and out of the cache memory and increases the operating speed of the system.
When a cache miss occurs and during store operations, it is necessary to replace the data in one of the elements of the set. Various algorithms are known in the art for selecting the cache cell to be replaced. These algorithms include random replacement, first-in first-out (FIFO) and least recently used (LRU). It is desirable to implement the replacement algorithm in minimum time and with a minimum of circuitry. The random approach provides relatively unpredictable behavior, while the least recently used technique requires that status be taken on every cache memory access. The FIFO approach, while not as effective as LRU, provides acceptable performance and is relatively easy to implement. The conventional means for implementing a FIFO algorithm is to maintain a separate status memory. The status memory is common for all the elements and tracks information for a particular index for all the elements. Whenever a block needs to be replaced, the status memory is queried for the appropriate element to be modified. During the element update, the status memory is modified to indicate which element should be updated the next time a block is to be modified. The problem with this method is that special control logic is required to update the status memory when any of the elements are modified.
A further consideration with respect to a cache memory is to insure high reliability and to minimize downtime. When the cache memory has only a single element for each index address, the system fails when a fault occurs in one of the cache cells. In a set associative cache memory, there are two or more cache cells available at each index address. However, the additional memory elements and the advent of high density memory devices tends to reduce reliability. It is desirable to provide a technique for maintaining system operation with slightly reduced capability when one of the cache cells in a set is defective.
It is a general object of the present invention to provide an improved cache memory for use in computer systems.
It is another object of the present invention to provide a cache memory having high availability to the user.
It is a further object of the present invention to provide a set associative cache memory including means for mapping out defective cache cells so that system operation can be continued.
It is yet another object of the present invention to provide a cache memory wherein status information is stored in distributed fashion in each of the cache cells.
It is yet another object of the present invention to provide a cache memory wherein a fault indicating bit is stored in each cache cell.
It is yet another object of the present invention to provide a cache memory wherein a single update bit used for controlling cache memory data replacement is stored in each cache cell.
It is a still further object of the present invention to provide a cache memory which is simple in construction and low in cost.